/*
 * @lc app=leetcode.cn id=403 lang=golang
 *
 * [403] 青蛙过河
 */

// 2.
// @lc code=start
func canCross(stones []int) bool {
	n := len(stones)
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	dp[0][0] = true
	for i := 1; i < n; i++ {
		for j := i - 1; j >= 0; j-- {
			k := stones[i] - stones[j]
			if k > j+1 {
				break
			}
			dp[i][k] = dp[j][k-1] || dp[j][k] || dp[j][k+1]
			if i == n-1 && dp[i][k] {
				return true
			}
		}
	}
	return false
}

// @lc code=end

// 1. 深度优先 超时 15/52
// @lc code=start
func canCross(stones []int) (ans bool) {
	var dfs func(i, step int)
	dfs = func(i, step int) {
		if i == len(stones)-1 {
			ans = true
			return
		}
		if i > len(stones)-1 || step <= 0 {
			return
		}

		for j := i + 1; j < len(stones); j++ {
			if (stones[i] + step) == stones[j] {
				dfs(j, step)
				dfs(j, step+1)
				dfs(j, step-1)
				continue
			}
		}
	}

	dfs(0, 1)
	return ans
}

// @lc code=end

